1. Field of the Invention
The present invention relates in general to placement and routing (P&R) tools for generating integrated circuit (IC) layouts and in particular to a method for enabling a P&R tool to determine when a power grid blocks input/output access to any terminal of a cell within an IC layout.
2. Description of Related Art
FIG. 1 is a simplified plan view of layers of a portion of a prior art integrated circuit 8 superimposed over one another, and FIG. 2 is a partial sectional elevation view of IC 8 of FIG. 1 along cut line 2—2. As illustrated in FIGS. 1 and 2, the various cells 10 of an integrated circuit are typically formed within a horizontally planar semiconductor substrate 22 aligned along a set rows 12 extending in an east-west direction. The cells 10 along each row 12 are normally of uniform height but vary in width. Depending on the density with which cells are packed along a row 12, not all space along each row 12 may be occupied by cells 10. Power and ground lines 14 and 16 also extending in the east/west direction parallel to each row 12 deliver power and ground signal to each cell 10 along the row. An array of ground lines 20 above cells 10, extending in a north/south direction on an IC layer 24 tie all of the east/west ground lines 16 together through vertically extending conductors (vias) 11. Similarly, an array of north/south power lines 18 residing on another layer 26 above cells 10 tie all of the east/west power lines 14 together through vias 13. Power lines 14 and 20 and ground lines 16 and 18 thus form separate power and ground distribution grids for distributing power and ground from the IC's external power and ground input/output terminals (not shown) to all cells 10.
North/south power and ground lines 18 and 20 are provided to help evenly distribute current loads on the individual east/west power or ground lines 14 or 16. When cells 10 along one row 12 draw an unusually large amount of supply current, not all of that current need be supplied through its adjacent east/west power and ground lines 14 and 16; the north/south lines 18 and 20 redirect current from more lightly loaded power and ground lines 14 and 16 serving nearby cell rows 12 to the cell rows that need it.
There has been a trend toward increasing the density of (i.e. reducing the distance between) the north/south power and ground lines 18 and 20 to more evenly distribute power on the grids. However increasing power line density makes it more difficult to position cells 10 along rows 12 because it increases the likelihood that power and ground conductors will block signal access to I/O terminals 25 on surfaces of cells 10 that communicate through vertical conductors (vias) 27 with conductors 29 on higher signal distribution layers 28 as shown in FIG. 2.
FIG. 3 is a simplified plan view of a cell 10 showing a set of conductive areas 32, 33 and 34 on the upper surface of the cell that act as the cell's input/output (I/O) terminals 25. As shown in FIG. 2, vias 27 extend upward from such input/output terminals on cells 10 to signal distribution layers 28 above the power and ground distribution layers 24 and 26. Conductors 29 residing on signal distribution layers 28 interconnect vias to form various signal paths between I/O terminals 25 of cells 10.
As illustrated in FIG. 4, when north/south power and ground lines 18 and 20 pass over a cell 10, one or more of those lines can completely cover one or more of the cell's I/O terminals 32-34, rendering them inaccessible to vias 27 of FIG. 2. In the example of FIG. 4, a power line 18 completely covering cell I/O terminal 32 blocks via access to that I/O terminal. As illustrated in FIG. 5, if cell 10 were to be moved slightly to the west, I/O terminal 32 would become accessible to a via. Although ground line 20 of FIG. 5 covers a portion of I/O terminal 34, a sufficient amount of area of each I/O terminal 32-34 is exposed to permit via access to each I/O terminal. Thus once a placement and routing (P&R) tool has initially positioned cells in an IC layout, it is necessary for the tool to determine whether power or ground lines block via access to I/O terminals of any of the cells, and then reposition cells to eliminate blockage.
FIG. 6 illustrates a prior art process of determining where each cell is to be placed in an IC and for also determining how the nets interconnecting cell I/O terminals are to be routed. An IC designer typically produces a high level IC design in the form of a netlist 40 referencing each cell to be included in an IC and indicating which of the various cell I/O terminals are to be interconnected to one another and which cell I/O terminals are to be connected to the IC's input and output terminals. A cell library 42 describes the layout of each type of cell that may be incorporated into the IC, and netlist 40 references each cell to be included in the IC by referencing the entry in cell library 42 describing that cell type. After creating netlist 40, the IC designer typically employs a computer-based placement and routing tool to generate a layout 44 including a placement plan indicating a position and orientation within rows 12 (FIG. 1) for each cell 10 referenced by netlist 40 and a routing plan describing how the conductors (nets) interconnecting I/O terminals of those cells are to be routed through the various layers and vias of the IC.
The P&R tool initially employs a placement algorithm 46 to produce the placement plan indicating the position of each cell 10 within one of cell rows 12 (FIG. 1). Placement algorithm 46 consults netlist 40 to determine which cells are to be included in the IC and consults cell library 42 to determine the size of each cell. Netlist 40 also tells placement algorithm 46 which cell terminals are to be connected to one another via nets, and the placement algorithm tries to position highly interconnected cells near one another to reduce net lengths.
After employing placement algorithm 46 to generate a placement plan establishing a position for each cell, the P&R tool employs a routing algorithm 48 that attempts to generate a routing plan indicating how each net is to be routed. When it is not possible for routing algorithm 48 to route each net, placement algorithm 46 modifies the placement plan to reposition cells, and routing algorithm 48 again attempts to develop a routing plan based on the modified placement plan. One or more such iterations may be needed before routing algorithm 48 is able to successfully produce a routing plan.
Constraint checking algorithms 50 check IC layout 44 routing plans forming IC layout 44 to determine whether they meet various constraints 52 on the IC layout. For example constraints 52 may place limits on signal delays through various signal paths within the IC or may place limits on the power density in an area of an IC. When the layout fails to meet one or more of constraints 52, placement and routing algorithms 46 and 48 are requested to modify the IC layout. Thus the P&R tool carries out a highly iterative process in which it may generate many different placement and routing plans in the process of developing an IC layout 44 satisfying all constraints 52.
When routing algorithm 48 finds that an I/O terminal of any cell is blocked by a power or ground line, it determines that the placement plan is unroutable and must be modified. The recent trend toward increasing the density of power and ground lines has increased the amount of time a P&R tool requires to generate a layout by increasing the likelihood of cell I/O terminal blockage, thereby increasing the likelihood that routing algorithm 48 will find any given placement plan produced by placement algorithm 64 to be unroutable. Since routing algorithm 48 typically requires substantial processing time when it tries to produce a routing plan, the placement and routing process could be speeded up if the P&R tool could prevent routing algorithm 48 from attempting to develop a routing plan for a version of a placement plan that is unroutable due to via blockage. Therefore what is needed is a computationally efficient method a P&R tool can use for quickly processing a placement plan to identify via blockages and for modifying the placement plan as necessary to eliminate such blockages before the P&R tool attempts to develop a routing plan.